Search for: All records

When visualizing a high-dimensional dataset, dimension reduction techniques are commonly employed which provide a single 2 dimensional view of the data. We describe ENS-t-SNE: an algorithm for Embedding Neighborhoods Simultaneously that generalizes the t-Stochastic Neighborhood Embedding approach. By using different viewpoints in ENS-t-SNE’s 3D embedding, one can visualize different types of clusters within the same high-dimensional dataset. This enables the viewer to see and keep track of the different types of clusters, which is harder to do when providing multiple 2D embeddings, where corresponding points cannot be easily identified. We illustrate the utility of ENS-t-SNE with real-world applications and provide an extensive quantitative evaluation with datasets of different types and sizes. 

A Stick graph is an intersection graph of axis-aligned segments such that the left end-points of the horizontal segments and the bottom end-points of the vertical segments lie on a “ground line,” a line with slope −1. It is an open question to decide in polynomial time whether a given bipartite graph G with bipartition A∪B has a Stick representation where the vertices in A and B correspond to horizontal and vertical segments, respectively. We prove that G has a Stick representation if and only if there are orderings of A and B such that G’s bipartite adjacency matrix with rows A and columns B excludes three small ‘forbidden’ submatrices. This is similar to characterizations for other classes of bipartite intersection graphs. We present an algorithm to test whether given orderings of A and B permit a Stick representation respecting those orderings, and to find such a representation if it exists. The algorithm runs in time linear in the size of the adjacency matrix. For the case when only the ordering of A is given, we present an O(|AB}^3)-time algorithm.